package com.mc.search;

public class VerifyBackSeries {
	//判断输入序列是否满足二叉搜索树的后序遍历序列
	public static boolean verify(int[] array){
		return verify(array, 0, array.length-1);
	}
	private static boolean verify(int[] array, int low, int high){
		
		if(low>high)
			return false;
		int root = array[high];
		int i=low;//左子树
		while(i<high&&array[i]<root)i++;
		int j=i;//右子树
		while(j<high){
			if(array[j]<root)
				return false;
			j++;
		}
		
		boolean left = true;
		boolean right = true;
		if(i>low)//左子树存在
			left = verify(array, low, i-1);
		if(i<high)//右子树存在
			right = verify(array, i, high-1);
		
		return left&&right;
	}
	public static void main(String[] args) {
		boolean result = VerifyBackSeries.verify(new int[]{5,7,6,9,11,10,8});
		System.out.println(result);
	}
}
